#pragma once

#include <vector>
#include <utility>

namespace sorting
{
    /**
     * @brief       希尔排序（采用2的幂次方增量序列）
     * @tparam  T   基本数据类型
     * @param   vec 基本数据类型的数组
     */
    template <typename T>
    void ShellSort_Exp2(std::vector<T> &vec)
    {
        using std::size_t;

        const size_t len = vec.size();
        if (len <= 1)
        {
            return;
        }

        // 初始增量 gap = len / 2，逐步缩小 gap
        for (size_t gap = len >> 1; gap > 0; gap >>= 1)
        {
            // 对每个子序列分别进行插入排序
            for (size_t i = gap; i < len; i++)
            {
                T tmp = vec[i];
                size_t j;
                // 插入排序逻辑，但步长为gap
                for (j = i; j >= gap && vec[j - gap] > tmp; j -= gap)
                {
                    vec[j] = vec[j - gap];
                }
                vec[j] = tmp;
            }
        }
    }

    /**
     * @brief       希尔排序（采用Knuth增量序列）
     * @tparam  T   基本数据类型
     * @param   vec 基本数据类型的数组
     */
    template <typename T>
    void ShellSort_Knuth(std::vector<T> &vec)
    {
        using std::size_t;

        const size_t len = vec.size();
        if (len <= 1)
        {
            return;
        }

        size_t gap = 1;
        while (gap < len / 3)
        {
            gap = gap * 3 + 1;
        }

        for (; gap > 0; gap /= 3)
        {
            for (size_t i = gap; i < len; ++i)
            {
                T tmp = vec[i];
                size_t j;
                for (j = i; j >= gap && vec[j - gap] > tmp; j -= gap)
                {
                    vec[j] = vec[j - gap];
                }
                vec[j] = tmp;
            }
        }
    }

    /**
     * @brief       希尔排序（采用Sedgewick增量序列）
     * @tparam  T   基本数据类型
     * @param   vec 基本数据类型的数组
     */
    template <typename T>
    void ShellSort_Sedgewick(std::vector<T> &vec)
    {
        using std::size_t;

        const size_t len = vec.size();
        if (len <= 1)
        {
            return;
        }

        // 动态生成Sedgewick增量序列
        std::vector<size_t> gaps;
        gaps.reserve(20); // 增量序列长度不用太大
        size_t i = 0;

        while (true)
        {
            size_t gap;
            if (i % 2 == 0)
            {
                gap = 9 * (1 << (2 * (i / 2))) - 9 * (1 << (i / 2)) + 1;
            }
            else
            {
                gap = (1 << (2 * ((i - 1) / 2 + 4))) - 3 * (1 << ((i - 1) / 2 + 2)) + 1;
            }

            if (gap >= len)
                break;
            gaps.push_back(gap);
            i++;
        }

        // 从大到小使用增量
        for (int s = static_cast<int>(gaps.size()) - 1; s >= 0; --s)
        {
            size_t gap = gaps[s];
            for (size_t k = gap; k < len; ++k)
            {
                T tmp = vec[k];
                size_t l;
                for (l = k; l >= gap && vec[l - gap] > tmp; l -= gap)
                {
                    vec[l] = vec[l - gap];
                }
                vec[l] = tmp;
            }
        }
    }
} // namespace sorting